#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/16 22:38
# @Author  : Yuyun
# @File    : 最长子字符串长度_字符lox.py
# @IDE     : PyCharm


"""
题目描述：
给你一个字符串s，字符串s首尾相连成一个环形，请你在环中找出l、o、x字符都恰好出现了偶数次最长子字符串的长度。
输入描述：
输入是一串小写的字母组成的字符串。
输出描述：
输出是一个整数
补充说明：
1<=s.length<=5x10^5
s只包含小写英文字母
示例1
输入： alolobo
输出：6
说明：
    最长子字符串之一是“alolob”，它包含'l'，'o'各2个，以及0个x'。
示例2
输入： looxdolx
输出： 7
说明：
	最长子字符串之" oxdolxl"，由于是首尾连接在一起的，所以最后一个‘x'和开头的’l‘是连接在一起的，
    此字符串包含'l'、’o‘、’x‘各2个。
示例3
输入： bcbebc
输出： 6
说明：
这个示例中，字符串“bcbcbc”本身就是最长的，因为'l'、'o'、'x'都出现了0
"""


def longest_balanced_substring(s: str) -> int:
    n = len(s)

    # 将字符串首尾相连，处理成双倍长度的字符串
    s = s + s

    # 状态压缩，初始状态为0，即'l'、'o'、'x'都出现偶数次
    state = 0

    # 用字典记录状态第一次出现的位置，初始化状态0的位置为-1
    pos = {0: -1}

    max_len = 0

    for i in range(2 * n):
        # 更新状态
        if s[i] == 'l':
            state ^= 1 << 0  # 翻转第0位（'l'）
        elif s[i] == 'o':
            state ^= 1 << 1  # 翻转第1位（'o'）
        elif s[i] == 'x':
            state ^= 1 << 2  # 翻转第2位（'x'）

        # 只计算不跨越长度 n 的子串
        if i >= n:
            # 防止子串跨过起点，减去长度超过n的部分
            if (i - n) in pos:
                del pos[i - n]

        # 如果当前状态已经出现过，计算子串长度
        if state in pos:
            max_len = max(max_len, i - pos[state])
        else:
            # 记录状态第一次出现的位置
            pos[state] = i

    # 结果不能超过原始字符串的长度 n
    return min(max_len, n)


# 测试
print(longest_balanced_substring("alolobo"))  # 输出: 6
print(longest_balanced_substring("looxdolx"))  # 输出: 7
print(longest_balanced_substring("bcbebc"))  # 输出: 6


